#ifndef INTSEGM_H
#define INTSEGM_H

#include "utils.h"
#include <math.h>
#include <memory.h>
#include <time.h>

typedef void (*PSeg);
typedef void (*PRegObj);

    //retuns if s1 below s2 at x
typedef int (*FBelow)(double x, PSeg s1, PSeg s2);
    /*finds all intersections of s1 and s2 and register them.
    If no_ip is true function doesn't find and register intersection pointints but only pairs.*/
typedef int (*FFindAndRegIPoints)(PSeg s1, PSeg s2, PRegObj intersection_registrator, BOOL no_ip);
    /*finds all intersection points of s1 and s2 in the stripe b, e and register them.
    If no_ip is true function doesn't find and register intersection pointints but only pairs.*/
typedef int (*FFindAndRegIPointsInStripe)(double b, double e, PSeg s1, PSeg s2, PRegObj intersection_registrator, BOOL no_ip);
    //puts a segment s end point coordinates into x and y
typedef void (*FGetPoint)(PSeg s, double &x, double &y);
    //returns TRUE if s2 begin point is above s1
typedef int (*FUnder)(PSeg s1, PSeg s2);
    //given X coord, returns Y coord of a segment s
typedef double (*FYAtX)(PSeg s, double X);
    /* register intersections of segments s1 and s2.
    intersection_registrator - object used to register intersections (for example pointer to some list to add intersections found)
    n - the number of the intesection points, p- pointer to intersection points array*/
typedef void (*FRegIntersection)(PRegObj intersection_registrator, PSeg s1, PSeg s2, int n, TPlaneVect *p);


const int undef_loc = -(int)2147483648;
const int inherit_each = 32;	// defines how often in optimal algorithm stairs are inherited, one inherited per inherit_each
const int max_call = 5;			//max number of sequential recursive call (opt)FindR before dividing current strip


struct EndIndexes
{
	int B, E;
};

struct ProgramStackRec //structure to use program stack to store list of starcases above current call
{
	ProgramStackRec *prev;	//link to program stack record storing parent staircase information 
	int Q_pos, right_bound;	//starting position and right boind of current staircase
	inline ProgramStackRec(int qp):Q_pos(qp){};
	inline ProgramStackRec(int qp, int rb):prev(NULL), Q_pos(qp), right_bound(rb){};
	inline ProgramStackRec *Set(ProgramStackRec *p, int rb){prev = p, right_bound = rb; return this;};
};


//uncomment line bellow to switch on counters
//#define COUNTERS_ON

#ifdef COUNTERS_ON
#define INC_COUNTER(i) (my_counter[i]++)
#define SET_COUNTER(i, value) my_counter[i] = value
#define ADD_COUNTER(i, value) my_counter[i] += value
#define SET_COUNTER_IFGT(i, value) if(value>my_counter[i])my_counter[i] = value
#else
#define INC_COUNTER(i) 
#define SET_COUNTER(i, value)
#define ADD_COUNTER(i, value)
#define SET_COUNTER_IFGT(i, value)
#endif

typedef int SegmentInfo;

struct no_ipSegmentInfo
{
	int s;
	double y;
	bool operator<(const no_ipSegmentInfo &p)
	{
		return y < p.y;
	};    
};

struct TEnd
{
	double x;
	bool islast;
	bool operator<(const TEnd &p)
	{
		return ((x < p.x) || ((x == p.x)&&(islast < p.islast)));
	};
};

struct TSEnd:public TEnd
{
	PSeg s;
};

struct TSegmEnd:public TEnd
{
	SegmentInfo s;
};

struct CSegmCompare
{
	PSeg *Scoll;
	FBelow _Below;
	double x;
	CSegmCompare()
	{};
	CSegmCompare(PSeg *sc, FBelow _b, double _x)
	{
		Scoll = sc;
		_Below = _b;
		x = _x;
	};
	bool lt(SegmentInfo s1, SegmentInfo s2)
	{
		return _Below(x, Scoll[s1], Scoll[s2]);
	}
};

struct TEvent
{
	TPlaneVect pt;
	int s1, s2;
};

class CIntersectionFinder
{
	int is_line_segments;//shows if segments is straitline and more fast calculations are possible

	//begin functions to deal with segments
	PRegObj _reg_obj;
	FBelow _Below;
	FFindAndRegIPoints _FindAndRegIPoints;
	FFindAndRegIPointsInStripe _FindAndRegIPointsInStripe;
	FGetPoint _BegPoint;
	FGetPoint _EndPoint;
	FUnder _Under;

	//for no_ip  strait line speedup 
	FYAtX _YAtX;
	FRegIntersection _RegIntersection;
	// end functions to deal with segments

	//begin strutures for Balaban algorithms
	//common
	int nTotSegm;
	EndIndexes *SegmentBE;
	TSegmEnd *ENDS;
	PSeg *Scoll;
	long int_numb;
	int LBoundIdx, RBoundIdx;
	double B, E;
	//for fast, optimal and parallel algorithms
	SegmentInfo * L, * R, * Q;
	//for no_ip algorithm
	no_ipSegmentInfo * no_ipL, * no_ipR, * no_ipQ;
	int *Loc;
	//end strutures for Balaban algorithms

	//private functions for Balaban algorithms

	//helpers for segment functions
	inline int IntersectionsInCurStripe(SegmentInfo  s1, PSeg s2)
	{
		INC_COUNTER(0);
		return _FindAndRegIPointsInStripe(B, E, Scoll[s1], s2, _reg_obj, dont_need_int_points);
	};

	inline int Intersections(SegmentInfo  s1, PSeg s2)
	{
		return _FindAndRegIPoints(Scoll[s1], s2, _reg_obj, dont_need_int_points);
	};

	inline void no_ipExchangeLR()
	{
		register no_ipSegmentInfo* tmp = no_ipL;
		no_ipL = no_ipR;
		no_ipR = tmp;
	};
	//common functions for fast algorithm
	void FreeMem();
	int prepare_ends(int n);

	//functions for no_ip algorithm
	void no_ipAllocMem();
	void no_ipFindInt(int QB, int QE, int l, PSeg s);
	void no_ipFindIntI(int r_index, ProgramStackRec * stack_pos, PSeg seg);
	void no_ipFindIntL(int QB, int QE, int segm_numb);
	int no_ipInsDel(int n, ProgramStackRec * stack_pos, int Size);
	int no_ipMerge(int QB, int QE, int Size);
	int no_ipSplit(int &step_index, int Size, int stripe_divided);
	int no_ipSearchInStrip(int QP, int Size);
	int no_ipFindR(int ladder_start_index, int interval_left_index, int interval_right_index, ProgramStackRec *stack_pos, int Size, int call_numb);


public:
	BOOL dont_need_int_points;/*shows that we need only intersecting pairs and
							  don't need to know a point where the pair intersects */

	// some counters to explore algorithm (not nessesary for functioning)
	double my_counter[8];

	CIntersectionFinder();
	~CIntersectionFinder(){FreeMem();};

	void set_segm_fuctions(FBelow _below, 
		FFindAndRegIPoints findAndRegIPoints, 
		FFindAndRegIPointsInStripe findAndRegIPointsInStripe, 
		FGetPoint begPoint, FGetPoint endPoint, 
		FUnder under, 
		FYAtX yAtX, 
		FRegIntersection regIntersection, 
		PRegObj reg_obj, 
		int is_line
		);

	void balaban_no_ip(int n, PSeg _Scoll[]);
};
#endif